package leetcode20211019;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LUYAO
 * Date: 2021-10-22
 * Time: 9:20
 */
public class Mathematical1 {
}

//数组中出现次数超过一半的数字
class Solution191 {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];

    }
}

//构建乘积数组,不能用除法
class Solution192 {
    public int[] constructArr(int[] a) {
        //[1,2,3,4,5]
        if (a == null || a.length == 0) return a;
        int len = a.length;
        int[] left = new int[len];
        int[] right = new int[len];
        left[0] = right[len - 1] = 1;

        for (int i = 1; i < len; i++) {
            left[i] = left[i - 1] * a[i - 1];
        }
        //left-->[1,1,2,6,24]
        for (int i = len - 2; i >= 0; i--) {
            right[i] = right[i + 1] * a[i + 1];
        }
        //right-->[120,60,20,5,1]
        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            ans[i] = left[i] * right[i];
        }
        return ans;
    }
}
